package com.mamingchao.foundation.arraysort.insertsort;

import com.mamingchao.foundation.arraysort.Sortable;

/**
 * Created by mamingchao on 2020/11/13.
 */
public class ClassicInsertSortImpl implements Sortable{

    @Override
    public void sort(int[] arr, int start, int end) {
        // check arg array

        if (arr == null || arr.length <2) {
            return;
        }
        int num = 0;

        for (int i = 1; i < arr.length  ; i++) {

            for (int j = i; j >0; j--) {
                num ++;
                //if the element is smaller than the previous element, then swap
                if(arr[j] < arr[j-1])  {
                    swap(arr,j,j-1);
                } else {
                    break;  // 加上break，循环次数 会少一些
                }
            }
        }
        System.out.println("循环次数 - " + num);
    }

    //这个版本的 swap 是有问题的，跟  a-b , a-b a+b 的那个问题是一样的
//    private static void swap(int[] arr,int i, int j){
//        arr[i] = arr[i]^arr[j];
//        arr[j] = arr[i]^arr[j];
//        arr[i] = arr[i]^arr[j];
//    }
}
